package arrays

/*
 * 冒泡排序
 */
func BubbleSort(values []int) {
	for i := 0; i < len(values)-1; i++ {
		for j := i + 1; j < len(values); j++ {
			if values[i] > values[j] {
				values[i], values[j] = values[j], values[i]
			}
		}
	}
}

/*
 * 冒泡排序 - 2
 */
func BubbleSort2(values []int) {
	for i := 0; i < len(values)-1; i++ {
		for j := 0; j < len(values)-1-i; j++ {
			if values[j] > values[j+1] {
				values[j], values[j+1] = values[j+1], values[j]
			}
		}
	}
}

/*
 * 选择排序
 *
 * 第一次从R[0]~R[n-1]选出最小值，与R[0]交换
 * 第二次从R[1]~R[n-1]选出最小值，与R[1]交换
 * ...
 * 第i次从R[i-1]~R[n-1]选出最小值，与R[i-1]交换
 * 第n-1次从R[n-2]~R[n-1]选出最小值，与R[n-2]交换
 */
func SelectSort(values []int) {

	var min int
	var minIndex int

	for k := 0; k < len(values)-1; k++ {
		min = values[k]
		minIndex = k
		for i := k + 1; i < len(values); i++ {
			if min > values[i] {
				min = values[i]
				minIndex = i
			}
		}
		if minIndex != k {
			values[k], values[minIndex] = values[minIndex], values[k]
		}

		//fmt.Printf("第%d次排序后结果: %v\n", k+1, values)
	}
}

/*
 * 插入排序
 *
 * 把n个待排序的元素看成一个有序表和一个无序表
 * 开始时有序表只包含一个元素，无序表包含n-1个元素
 * 排序过程中每次从无序表取出第一个元素
 * 把它依次与有序表元素比较
 * 将它插入到有序表的适当位置
 */
func InsertSort(values []int) {

	for i := 1; i < len(values); i++ {
		value := values[i]
		insertIndex := i - 1
		for ; insertIndex >= 0; insertIndex-- {
			if values[insertIndex] < value {
				break
			}
			values[insertIndex+1] = values[insertIndex]
		}
		if insertIndex+1 != i {
			values[insertIndex+1] = value
		}

		//fmt.Printf("第%d次排序结果: %v\n", i, values)
	}
}

/*
 * 快速排序
 *
 * 对冒泡排序的改进
 * 通过一趟排序将数据分割成独立的两部分
 * 其中一部分的所有数据都比另一部分小
 * 然后按照此方法对这两部分数据分布进行快速排序
 * 整个排序过程可以递归进行
 */
func QuickSort(values []int) {
	quickSort(0, len(values)-1, values)
}

// 1. left表示数组左边的下标
// 2. right表示数组右边的下标
// 3  array表示要排序的数组
func quickSort(left int, right int, array []int) {

	l := left
	r := right
	// pivot是中轴
	pivot := array[(left+right)/2]
	temp := 0

	// for循环的目标是将比pivot小的数放到左边
	// 比pivot大的数放到右边
	for l < r {
		// 从pivot的左边找到大于等于pivot的值
		for array[l] < pivot {
			l++
		}
		// 从pivot的右边边找到小于等于pivot的值
		for array[r] > pivot {
			r--
		}
		// 1 >= r表明本次分解任务完成
		if l >= r {
			break
		}
		// 交换
		temp = array[l]
		array[l] = array[r]
		array[r] = temp
		// 优化
		if array[l] == pivot {
			r--
		}
		if array[r] == pivot {
			l++
		}
	}
	// 如果1== r再移动下
	if l == r {
		l++
		r--
	}
	// 向左递归
	if left < r {
		quickSort(left, r, array)
	}
	// 向右递归
	if right > l {
		quickSort(l, right, array)
	}
}

/*
 * 二分查找
 */
func BinarySearch(values []int, targetValue int) int {

	var min = 0
	var max = len(values) - 1
	var mid = 0

	for max >= min {

		mid = (min + max) >> 1

		if values[mid] > targetValue {
			max = mid - 1
		} else if values[mid] < targetValue {
			min = mid + 1
		} else {
			return mid
		}
	}

	return -1
}

/*
 * 二分查找 - 递归方式
 */
func BinarySearch2(values []int, targetValue int) int {
	return binarySearch2(values, targetValue, 0, len(values)-1)
}

/*
 * 二分查找 - 递归方式
 */
func binarySearch2(values []int, targetValue int, min int, max int) int {

	var mid = 0

	if max >= min {

		mid = (min + max) >> 1

		if values[mid] > targetValue {
			return binarySearch2(values, targetValue, min, mid-1)
		} else if values[mid] < targetValue {
			return binarySearch2(values, targetValue, mid+1, max)
		} else {
			return mid
		}
	}

	return -1
}

/*
 * 向有序切片里面插入元素
 */
func BinarySearchInsert(values []int, value int) []int {

	// 查找元素存放的索引
	index := binaryInsertIndex(values, value)

	// 插入元素
	return Insert(values, index, value)
}

/*
 * 向有序切片里面插入元素 - 查找元素存放的索引
 */
func binaryInsertIndex(values []int, targetValue int) int {

	var min = 0
	var max = len(values) - 1
	var mid = 0

	for max >= min {

		mid = (min + max) >> 1

		if values[mid] > targetValue {
			max = mid - 1
		} else if values[mid] < targetValue {
			min = mid + 1
		} else {
			return mid
		}
	}

	return min
}

/*
 * 插入
 */
func Insert(values []int, index int, value int) []int {
	return append(values[:index], append([]int{value}, values[index:]...)...)
}

/*
 * 删除
 */
func Remove(values []int, index int) []int {
	return append(values[:index], values[index+1:]...)
}

/*
 * 斐波那契数列
 */
func FibonacciSequence(count int) []int {

	var values []int
	values = make([]int, count)

	values[0] = 1
	values[1] = 1

	for i := 2; i < count; i++ {
		values[i] = values[i-1] + values[i-2]
	}

	return values
}

/*
 * 斐波那契数
 */
func FibonacciValue(index int) int {

	if index == 1 || index == 2 {
		return 1
	}

	return FibonacciValue(index-1) + FibonacciValue(index-2)
}
